// Copyright 2022 Hollson. All rights reserved.
// Use of this source code is governed by a MIT style
// license that can be found in the LICENSE file.

package leetcode1

import (
	"sort"
)

// https://leetcode-cn.com/problems/assign-cookies/

// 示例：
func findContentChildren(greed, size []int) (ans int) {
	sort.Ints(greed)
	sort.Ints(size)
	n, m := len(greed), len(size)
	for i, j := 0, 0; i < n && j < m; i++ {
		for j < m && greed[i] > size[j] {
			j++
		}
		if j < m {
			ans++
			j++
		}
	}
	return
}

// 第一种思路:优先满足胃口大的
func findContentChildrenV1(g []int, s []int) int {
	sort.Ints(g)
	sort.Ints(s)
	index := len(s) - 1
	count := 0
	for i := len(g) - 1; i >= 0; i-- {
		if index >= 0 && g[i] <= s[index] {
			index--
			count++
		}
	}
	return count
}

// 第二种思路:优先满足胃口小的
func findContentChildrenV2(g []int, s []int) int {
	sort.Ints(g)
	sort.Ints(s)
	index, count := 0, 0
	for i := 0; i < len(s); i++ {
		if index < len(g) && g[index] <= s[i] {
			count++
			index++
		}
	}
	return count
}

// 排序后，局部最优
// https://leetcode-cn.com/problems/assign-cookies/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-tan-x-6jsc/
// https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E4%BB%80%E4%B9%88%E6%98%AF%E8%B4%AA%E5%BF%83
func findContentChildrenV3(g []int, s []int) int {
	sort.Ints(g)
	sort.Ints(s)

	// 从小到大
	child := 0
	for sIdx := 0; child < len(g) && sIdx < len(s); sIdx++ {
		if s[sIdx] >= g[child] { // 如果饼干的大小大于或等于孩子的为空则给与，否则不给予，继续寻找选一个饼干是否符合
			child++
		}
	}
	return child
}
